1. Field of the Invention
The invention relates to concurrency control and, in particular, to lock management techniques that allow efficient bulk delegation of locks in database and/or transaction processing systems.
2. Description of the Related Art
Delegation of locks forms a basis for concurrency control in many modern transaction models, such as nested transaction models (see e.g., J. E. B. Moss, Nested Transactions: An Approach to Reliable Distributed Computing, Ph.D. thesis, Massachusetts Institute of Technology, April 1981; T. Harder and K. Rothermel. Concurrency Control Issues in Nested Transactions, VLDB Journal, 2(1):39-74, 1993), split-join transaction models (see e.g., C. Pu, G. E. Kaiser, and N. Hutchinson, Split-Transactions for Open-Ended Activities, In Proc. of the ACM SIGMOD Int. Conf. on Management of Data, pp. 26-37, 1988; G. E. Kaiser and C. Pu, Dynamic Restructuring of Transactions, In Database Transaction Models for Advanced Applications, Data Management Systems, Morgan-Kaufman, pp. 266-295, 1992), colored actions (see e.g., S. K. Shrivastava and S. M. Wheater, Implementing Fault-Tolerant Distributed Applications Using Objects and Multi-coloured Actions, In Proc. of the Int. Conf. on Distributed Computing Systems, pp. 203-210, 1990), or the Apotram transaction model (see O. Anfindsen, Apotram—an Application-Oriented Transaction Model, Ph.D. thesis, University of Oslo, Department of Informatics, 1997). Various of these models are characterized by the delegation of locks at some point in the life of a transaction or assimilated entity. For example, the join operation of split-join transactions is a straightforward use of lock delegation. In the nested transaction model, a sub-transaction delegates all its locks to its parent transaction upon its commit. Similarly, lock delegation can be used to achieve the effect of moving objects upward or downward in a hierarchy of nested databases. Typically, a transaction model that imposes hierarchical structure and relies on locking for concurrency control uses some form of lock delegation to control lock ownership across levels of the hierarchy.
Often, transaction models assume that a transaction may delegate a single lock or a specific subset of its locks to other transactions. Often, it is desirable to delegate locks in bulk. For example, bulk delegation is assumed for most hierarchical transaction models, such as the nested transaction model, where delegation is useful to transfer the locks of a committed transaction to the next transaction up the hierarchy. Because commitment of a nested transaction is a common case, special attention should be paid to optimize bulk delegation. Unfortunately, most implementations focus on the case of single lock delegation and do not pay particular attention to efficiency of bulk delegation, instead implementing bulk delegation as a sequence of single lock delegation operations. Typically, such implementations of bulk delegation involve traversing and updating linked-lists of lock request control blocks (LRCBs). Scaling performance of such implementations is poor.
One alternative bulk delegation technique is the applicants own prior work (described in L. Daynes, M. P. Atkinson, and P. Valduriez, Efficient Support for Customizing Concurrency Control in Persistent Java, In E. Bertino, S. Jajodia, and L. Kerschberg, editors, International Workshop on Advanced Transaction Models and Architectures (ATMA), pp. 216-233, Goa, India, September 1996). Using that technique, the effect of a bulk lock delegation is achieved not by updating individual locks, but by changing the conflict detection mechanisms of the delegatee, using a lock manager ability's to represent ignore-conflict relationships between transactions. Unfortunately, while that technique tends to decouple the cost of bulk delegation from the number of locks delegated, it still suffers from poor scaling performance because space used to represent locks grows in proportion with the number of locks represented.
What is needed are low-space overhead techniques that facilitate efficient bulk delegation, particularly in implementations that demand fine-granularity locking and in which transactions tend to acquire large numbers of locks.